package code;

import java.util.ArrayList;
import java.util.List;

public class Code51 {
	
	/*
	 * N-Queens
	 * dfs生成
	 */
	public void generateNQueens(int n,int x,int[] Y,List<String[]> list){
		/*
		 * 已经添加完了吗？
		 */
		int i,j;
		if(x==n){
			String[] rec=new String[n];
			for(i=0;i<n;i++){
				StringBuilder sb=new StringBuilder();
				for(j=0;j<n;j++){
					if(Y[i]==j)
						sb.append("Q");
					else
						sb.append(".");
				}
				rec[i]=sb.toString();
			}
			list.add(rec);
		}
		for(i=0;i<n;i++){
			if(isOk(i,Y,x)){
				Y[x]=i;
				generateNQueens(n,x+1,Y,list);
			}
		}
	}
	/*
	 * 判断第x行的第y列是否能放Queen,Y[0..x]保存的是已经放的Queen
	 */
	public boolean isOk(int y,int[] Y,int x){
		
		for(int i=0;i<x;i++){
			if(Y[i]==y)
				return false;
			/*
			 * 在对角线上？
			 */
			if(Math.abs(x-i)==Math.abs(y-Y[i]))
				return false;
		}
		return true;
	}
	
    public List<String[]> solveNQueens(int n) {
    	List<String[]> result=new ArrayList<String[]>();
    	int[] Y=new int[n];
    	generateNQueens(n, 0, Y, result);
    	
    	return result;
    }
    
    public static void main(String[] args){
    	Code51 code=new Code51();
    	for(int i=4;i<20;i++){
    		List<String[]> ans=code.solveNQueens(i);
    		System.out.println(i+"----> "+ans.size());
    	}
    }
}
